#define _CRT_SECURE_NO_WARNINGS 1


class Solution {
public:
    int ladderLength(string beginWord, string endWord,
        vector<string>& wordList) {
        int ret = 1;
        string change = "abcdefghijklmnopqrstuvwxyz";
        int length = beginWord.size();
        unordered_set<string> visit;
        unordered_set<string> list(wordList.begin(), wordList.end());
        if (!list.count(endWord)) {
            return 0;
        }
        queue<string> q;
        q.push(beginWord);
        while (!q.empty()) {
            int sz = q.size();
            ret++;
            for (int i = 0; i < sz; i++) {
                string s = q.front();
                q.pop();
                for (int i = 0; i < length; i++) {
                    string tmp = s;
                    for (int j = 0; j < 26; j++) {
                        tmp[i] = change[j];
                        if (!visit.count(tmp) && list.count(tmp)) {
                            if (tmp == endWord) {
                                return ret;
                            }
                            visit.insert(tmp);
                            q.push(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};